//
// Created by Snow on 2023/4/25.
//
#include<cstdio>
#define MAXL 100//最大长度
typedef int KeyType;//定义关键字类型为int
typedef char InfoType;
typedef struct
{
    KeyType key;//关键字项
    InfoType data;//其他数据项，类型为InfoType
}RecType;//查找元素的类型
//顺序表基本运算算法
void CreateList(RecType R[],const KeyType keys[],int n)//创建顺序表
{
    for(int i=0;i<n;i++)
        R[i].key=keys[i];
}
void DispList(RecType R[],int n)//输出顺序表
{
    for(int i=0;i<n;i++)
        printf("%d ",R[i].key);
    printf("\n");
}
int BinSearch(RecType R[],int n,KeyType k)//折半查找法
{
    int low=0,high=n-1,mid;
    while(low<=high)//当前区间存在元素时循环
    {
        mid=(low+high)/2;
        if(k==R[mid].key)//查找成功是返回逻辑序号
            return mid+1;
        if(k<R[mid].key)//继续在R[low...mid-1]中查找
            high=mid-1;
        else//k>R[mid].key
            low=mid+1;//继续在R[mid+1..high]中查找
    }
    return 0;//未找到时返回0（查找失败
}
int main()
{
    int n=11;
    RecType R[MAXL];
    KeyType a[]={2,3,10,15,20,25,28,29,30,35,40},k=20;
    CreateList(R,a,n);
    DispList(R,n);
    printf("R[%d]=%d\n",BinSearch(R,n,k),k);
    return 1;
}
